|
Farkas's lemma is a result in mathematics stating that a vector is either in a given convex cone or that there exists a (hyper)plane separating the vector from the cone—there are no other possibilities. It was originally proven by the Hungarian mathematician Gyula Farkas. It is used amongst other things in the proof of the Karush–Kuhn–Tucker theorem in nonlinear programming. Farkas's lemma is an example of a theorem of alternatives: a theorem stating that of two systems, one or the other has a solution, but not both nor none. == Statement of the lemma == Let ''A'' be a real ''m'' × ''n'' matrix and ''b'' an ''m''-dimensional real vector. Then, exactly one of the following two statements is true: # There exists an ''x'' ∈ R''n'' such that ''Ax'' = ''b'' and ''x'' ≥ 0. # There exists a ''y'' ∈ R''m'' such that ''yTA'' ≥ 0 and ''yTb'' < 0. Here, the notation ''x'' ≥ 0 means that all components of the vector ''x'' are nonnegative. If we write ''C(A)'' for the cone generated by the columns of ''A'', then the vector ''x'' proves that ''b'' lies in ''C(A)'' while the vector ''y'' gives a linear functional that separates ''b'' from ''C(A)''. There are a number of slightly different (but equivalent) formulations of the lemma in the literature. The one given here is due to . 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Farkas' lemma」の詳細全文を読む スポンサード リンク
|